I. Field
The following description relates generally to data communication and more particularly to efficient classification of network packets and scalable firewalls.
II. Background
Firewalls are a type of system designed to protect unauthorized access to or from a private network and can be implemented in hardware, software, or a combination of both hardware and software. The recent trend in firewall protection is toward “personal firewalls.” The security benefits of this trend have been positive and have provided an improvement in configurability, utility, and (in the case of mobile devices) portability of firewalls. This is referred to as the “every node is a firewall” model, which presumes the underlying fundamental economic assumption that the cost of delivery of unwanted packets is negligible. This economic assumption is not always correct, especially in the realm of wireless communication.
To be effective in contexts where packet delivery costs are not negligible, firewalls should mitigate the volume of unwanted traffic; even a small reduction of such unwanted traffic is a net gain. The more precisely a firewall policy fits the actual traffic requirements of a legitimate node population, the more effective the policy and the greater the mitigation of unwanted traffic volume. Therefore, firewalls in these contexts should permit remote ad hoc updates to the policy from authorized sources.
A common type of firewall is a packet filter that passes or blocks packets, but otherwise leaves the traffic flow untouched. At the core of each packet filter is a mechanism that classifies packets according to a supplied policy. Stateful packet filters (such as OpenBSD's pf) possess scalable mechanisms for processing packets that belong to established traffic flows. Packets that do not belong to an established flow are classified according to a policy, which is expressed as a set of rules. Rules are generally processed in sequence order to assess each packet.
Some packet classifiers employ optimization techniques to their rule sets in order to speed up packet processing. Facilities for early termination of rule processing under specified circumstances are common. A more sophisticated example is pf's skipsteps, which enable predictive skipping when contiguous rule blocks could never match a packet. Such techniques can be very effective if the rule set is highly ordered and exhibits strong commonality in rule criteria. However, in a highly dynamic environment, where there are ongoing incremental updates to the rule set, these conditions are not generally met.
Traditionally, classifier rule sets tend to be quite static in nature, and are often updated through a manual process. Since extant classifiers typically exhibit sequence dependent behavior, it is generally difficult to insert and remove arbitrary rules from a policy without unwanted or unintended side effects.
Nodes protected by a centralized packet filter may wish to extend service (typically by listening for packets that initiate a flow) at any time. Similarly, they may wish to retract previously offered services. This is consistent with the Internet end-to-end model. If the maximum number of unwanted packets is to be blocked while allowing ad hoc service extension and retraction, the filtering policy must be dynamically updated by nodes as changes occur. The filter should also have a mechanism (such as keep-alives) to discover when a node departs the network abruptly, so that obsolete rules can be removed from the policy in a timely fashion.